/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.discovery;

import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

public class ParetoSet<T extends SolutionCandidate> {
	
	private TreeSet<T> set;
	private int objectives;
	
	public ParetoSet(int objectives) {
		if (objectives<1) throw new IllegalArgumentException();
		if (objectives>2) throw new IllegalArgumentException("Not implemented for more than 2 objectives.");
		set = new TreeSet<T>(new SolutionComparator());
		this.objectives = objectives;
	}

	private class SolutionComparator implements Comparator<SolutionCandidate> {
		@Override
		public int compare(SolutionCandidate s1, SolutionCandidate s2) {
			int l = s1.getObjectiveCount(); 
			if (l!=s2.getObjectiveCount()) throw new IllegalArgumentException("Incompatible solution candidates.");
			for (int i=0; i<l; ++i) {
				if (s1.getObjectiveScore(i)<s2.getObjectiveScore(i)) return -1;
				if (s1.getObjectiveScore(i)>s2.getObjectiveScore(i)) return 1;
				if (Double.isNaN(s1.getObjectiveScore(i))) {
					if (Double.isNaN(s2.getObjectiveScore(i))) continue;
					return -1;
				}
				if (Double.isNaN(s2.getObjectiveScore(i))) {
					if (Double.isNaN(s1.getObjectiveScore(i))) continue;
					return 1;
				}
			}
			return s1.compareTo(s2);
		}
	}

	/** Returns true iff solution1 dominates solution2. */
	private boolean dominates(T solution1, T solution2) {
		boolean equal = true;
		for (int i=0; i<objectives; ++i) {
			if (solution1.getObjectiveScore(i)<solution2.getObjectiveScore(i)) return false;
			if (solution1.getObjectiveScore(i)>solution2.getObjectiveScore(i)) equal = false;
		}
		return !equal;
	}
	
	private void removeDominated(T solution) { 
		SortedSet<T> headSet = set.headSet(solution);
		while (!headSet.isEmpty()) {
			T last = headSet.last();
			if (dominates(solution, last)) headSet.remove(last);
			else break;
		}
	}
	
	/** Considers the first n-1 scores of given solution (where n is the total
	 *  number of objectives). The last score of given solution must be unknown (i.e. equal NaN).
	 *  @return Returns a threshold t such that solution would be 
	 *          dominated by the pareto set iff the last score was <t. */
	public double dominationThreshold(T solution) {
		if (!Double.isNaN(solution.getObjectiveScore(objectives-1))) throw new IllegalArgumentException("NaN expected for last score.");
		if (objectives==1) {
			if (set.isEmpty()) return Double.NEGATIVE_INFINITY;
			return set.last().getObjectiveScore(0); 
		} else if (objectives==2) {
			SortedSet<T> tailSet = set.tailSet(solution);
			if (tailSet.isEmpty()) return Double.NEGATIVE_INFINITY;
			Iterator<T> it = tailSet.iterator();
			T t = it.next();
			while (it.hasNext()) {
				T t2 = it.next();
				if (t.getObjectiveScore(0)==t2.getObjectiveScore(0)) t = t2;
				else break;
			}
			return t.getObjectiveScore(1);
		} else {
			throw new IllegalStateException();
		}
	}
	
	/** Updates the pareto set by examining (and possibly adding) another solution. 
	 *  This possibly leads to the removal of other (now dominated) solutions. 
	 *  @return Returns true if given solution was added to the pareto set.
	 */
	public boolean update(T newSolution) {
		if (newSolution.getObjectiveCount()!=objectives) throw new IllegalArgumentException();
		SortedSet<T> tailSet = set.tailSet(newSolution);
		if (tailSet.isEmpty() || !dominates(tailSet.first(),newSolution)) {
			set.add(newSolution);
			removeDominated(newSolution);
			return true;
		}
		return false;
	}
	
	/** Checks whether the given solution is dominated by any solution in the
	 *  pareto set. Does not change the pareto set.
	 */
	public boolean isDominated(T newSolution) {
		if (newSolution.getObjectiveCount()!=objectives) throw new IllegalArgumentException();
		if (objectives==1) {
			if (set.isEmpty()) return false;
			return newSolution.getObjectiveScore(0)<set.last().getObjectiveScore(0); 
		}
		SortedSet<T> tailSet = set.tailSet(newSolution);
		return !tailSet.isEmpty() && dominates(tailSet.first(),newSolution);
	}
	
	public SortedSet<T> getParetoSet() {
		return set;
	}

	@Override
	public String toString() {
		return set.toString();
	}
	
}
